//给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 
//
// 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次
//。如果 h 有多种可能的值，h 指数 是其中最大的那个。 
//
// 
//
// 示例 1： 
//
// 
//输入：citations = [3,0,6,1,5]
//输出：3 
//解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
//     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。 
//
// 示例 2： 
//
// 
//输入：citations = [1,3,1]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// n == citations.length 
// 1 <= n <= 5000 
// 0 <= citations[i] <= 1000 
// 
//
// Related Topics 数组 计数排序 排序 👍 410 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2023-10-29 22:19:46
 * @description 274.H 指数
 */
public class HIndex{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new HIndex().new Solution();
		solution.hIndex(new int[]{3,0,6,1,5});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //排序（可以用二分优化）
    public int hIndex1(int[] citations) {
		Arrays.sort(citations);
		int n = citations.length;
		int i;
		for (i = n-1; i >=0 ; i--) {
			if(citations[i]<=n-i) return Math.max(citations[i],n-i-1);
		}
		return n-i-1;
    }
	//计数排序
	public int hIndex2(int[] citations) {
		int n=citations.length,sum=0;
		//引用次数大于数组长度的，用同一个数字表示，其余位置统计计数
		int [] ar=new int[n+1];
		for (int i = 0; i < n; i++) {
			if(citations[i]>=n){
				ar[n]++;
			}else {
				ar[citations[i]]++;
			}
		}
		//累计得到大于或等于当前引用次数 i 的总论文数
		for (int i = n; i >=0 ; i--) {
			sum+=ar[i];
			if(sum>=i) return i;
		}
		return 0;
	}
	//二分,答案具有单调性，直接枚举0~n中的数，然后缩小边界
	public int hIndex(int[] citations) {
		int l=0,r=citations.length;
		int m=0,cnt=0;
		while (l<=r){
			m=l+((r-l)>>1);
			 cnt=0;
			for (int i = 0; i < citations.length; i++) {
				if(citations[i]>=m) cnt++;
			}
			//答案在m,r中
			if(cnt>=m){
				l=m+1;
				//答案在0,m中
			}else {
				r=m-1;
			}
		}
		return r;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
